/**
 * 给你一个字符串s和一个字符规律p，请你来实现一个支持 '.'和'*'的正则表达式匹配。
 *
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。
 *
 * 链接：https://leetcode.cn/problems/regular-expression-matching
 * 题解：https://labuladong.gitee.io/algo/3/28/90/
 */

import java.util.HashMap;
import java.util.Map;

class IsMatch {
    /**
     * 递归版动规
     */
    Map<String,Boolean> map=new HashMap<>();
    public boolean isMatchDp(String s, String p) {
        return dp(s,0,p,0);
    }
    public boolean dp(String s,int i,String p,int j) {
        if(j==p.length()) {
            return i==s.length();
        }
        if(i==s.length()) {
            int n=p.length();
            if((n-j)%2==1) {
                return false;
            }
            //如果是a*b*...可以表示空串，可以匹配
            for(;j+1<n;j+=2) {
                if(p.charAt(j+1)!='*') {
                    return false;
                }
            }
            return true;
        }
        boolean res=false;
        String str=Integer.toString(i)+','+Integer.toString(j);
        if(map.containsKey(str)) {//备忘录去除重复子问题
            return map.get(str);
        }
        if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='.') {//如果s[i]==p[j]
            if((j+1<p.length())&&(p.charAt(j+1)=='*')) {//如果p[j+1]=='*',看p[j]匹配0个还是多个
                res=dp(s,i,p,j+2)||dp(s,i+1,p,j);
            } else {
                res= dp(s,i+1,p,j+1);
            }
        } else {//如果s[i]!=p[j]
            if(j+1<p.length()&&p.charAt(j+1)=='*') {
                res= dp(s,i,p,j+2);
            } else {
                res= false;
            }
        }
        map.put(str,res);
        return res;
    }

    /**
     * 迭代版递归
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j - 2] || f[i - 1][j];
                    }
                    else {
                        f[i][j] = f[i][j - 2];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }

}